home *** CD-ROM | disk | FTP | other *** search
/ The Utilities Experience / The Utilities Experience - Volume 1.iso / software / misc / o-z / x-windows / gs262 / iname.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-29  |  8.5 KB  |  281 lines
  1. /* Copyright (C) 1989, 1992, 1993 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* iname.c */
  20. /* Name lookup for Ghostscript interpreter */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "alloc.h"
  24. #include "errors.h"
  25. #include "iname.h"
  26. #include "ivmspace.h"
  27. #include "store.h"
  28.  
  29. /* Definitions and structure for the name table. */
  30. /* The first entry is left unused. */
  31. /* 1-character names are the next nt_1char_size entries. */
  32. #define nt_log2_sub_size 7
  33. #define nt_sub_size (1 << nt_log2_sub_size)
  34. #define nt_sub_index_mask (nt_sub_size - 1)
  35. #define nt_hash_size 256        /* must be a power of 2 */
  36. #define nt_1char_size 128
  37. typedef name name_sub_table[nt_sub_size];
  38. typedef struct {
  39.     ushort hash[nt_hash_size];
  40.     name *table[1 << (16 - nt_log2_sub_size)];    /* name_sub_table */
  41.     ref count;            /* t_integer */
  42. #define nt_count(nt) (uint)((nt)->count.value.intval)
  43. #define set_nt_count(nt,cnt) ((nt)->count.value.intval = (cnt))
  44. } name_table;
  45. #define name_index_ptr(nt, index)\
  46.   ((nt)->table[(index) >> nt_log2_sub_size] + ((index) & nt_sub_index_mask))
  47.  
  48. /*
  49.  * Scramble the assignment order within a sub-table, so that
  50.  * dictionary lookup doesn't have to scramble the index.
  51.  * The algorithm must have three properties:
  52.  *    - It must map 0 to 0;
  53.  *    - It must only scramble the sub-table index;
  54.  *    - It must be a permutation on the sub-table index.
  55.  * We do something very simple for now.
  56.  */
  57. #define name_count_to_index(cnt)\
  58.   (((cnt) & (-nt_sub_size)) + (((cnt) * 59) & nt_sub_index_mask))
  59. /* We also store the reverse permutation, for age checking in restore. */
  60. #define name_index_to_count(idx)\
  61.   ((idx) ^ name_sub_index_to_count[(idx) & nt_sub_index_mask])
  62. #if nt_sub_size <= 256
  63. private byte name_sub_index_to_count[nt_sub_size];
  64. #else
  65. private ushort name_sub_index_to_count[nt_sub_size];
  66. #endif
  67.  
  68. /* The one and only name table (for now). */
  69. private name_table *the_nt;
  70.  
  71. /* Forward references */
  72. private int name_alloc_sub(P1(name_table *));
  73. #ifdef AMIGA
  74. extern uint string_hash(const byte *, uint); /* from gsutil.c */
  75. extern void gs_exit(int); /* from gsmain.c */
  76. #endif
  77.  
  78. /* Make a t_name ref out of a name * */
  79. #define make_name(pref, idx, pnm)\
  80.   make_tasv(pref, t_name, 0, idx, pname, pnm)
  81.  
  82. /* Initialize the name table */
  83. void
  84. name_init(void)
  85. {    register uint i;
  86.     static byte one_char_names[nt_1char_size];
  87.     uint local = alloc_select_local(0);
  88.     /* Initialize the index_to_count map. */
  89.     for ( i = 0; i < nt_sub_size; i++ )
  90.        {    uint idx = name_count_to_index(i);
  91.         name_sub_index_to_count[idx] = idx ^ i;
  92.        }
  93.     the_nt = (name_table *)alloc(1, sizeof(name_table), "name_init");
  94.     memset(the_nt, 0, sizeof(name_table));
  95.     make_int(&the_nt->count, 1);
  96.     /* Initialize the one-character names. */
  97.     for ( i = 0; i < nt_1char_size; i++ )
  98.        {    uint ncnt = i + 1;
  99.         uint nidx = name_count_to_index(ncnt);
  100.         register name *pname;
  101.         if ( the_nt->table[nidx >> nt_log2_sub_size] == 0 )
  102.             name_alloc_sub(the_nt);
  103.         pname = name_index_ptr(the_nt, nidx);
  104.         set_nt_count(the_nt, ncnt + 1);
  105.         one_char_names[i] = i;
  106.         pname->string_size = 1;
  107.         pname->string_bytes = &one_char_names[i];
  108.         pname->pvalue = pv_no_defn;
  109.        }
  110.     alloc_select_local(local);
  111. }
  112.  
  113. /* Look up or enter a name in the table. */
  114. /* Return 0 or an error code. */
  115. /* The return may overlap the characters of the string! */
  116. /* See iname.h for the meaning of enterflag. */
  117. int
  118. name_ref(const byte *ptr, uint isize, ref *pref, int enterflag)
  119. {    register name *pname;
  120.     const byte *cptr;
  121.     ushort size = (ushort)isize;    /* see iname.h */
  122.     uint nidx;
  123.     if ( size == 1 && *ptr < nt_1char_size )
  124.        {    uint ccnt = *ptr + 1;
  125.         nidx = name_count_to_index(ccnt);
  126.         pname = name_index_ptr(the_nt, nidx);
  127.         make_name(pref, nidx, pname);
  128.         return 0;
  129.        }
  130.     else
  131.        {    ushort *phash =
  132.           the_nt->hash +
  133.             ((ushort)string_hash(ptr, size) & (nt_hash_size - 1));
  134.         uint ncnt;
  135.         nidx = *phash;
  136.         while ( nidx != 0 )
  137.            {    pname = name_index_ptr(the_nt, nidx);
  138.             if ( pname->string_size == size &&
  139.                  !memcmp(ptr, pname->string_bytes, size)
  140.                )
  141.                {    make_name(pref, nidx, pname);
  142.                 return 0;
  143.                }
  144.             nidx = pname->next_index;
  145.            }
  146.         /* Not in table, allocate a new entry. */
  147.         if ( enterflag < 0 )
  148.             return_error(e_undefined);
  149.         if ( !(nt_count(the_nt) & (nt_sub_size - 1)) )
  150.            {    int code = name_alloc_sub(the_nt);
  151.             if ( code < 0 ) return code;
  152.            }
  153.         ncnt = nt_count(the_nt);
  154.         nidx = name_count_to_index(ncnt);
  155.         pname = name_index_ptr(the_nt, nidx);
  156.         pname->next_index = *phash;
  157.         *phash = nidx;
  158. #ifdef DEBUG
  159.         if ( debug_c('n') )
  160.         {    uint ci;
  161.             dprintf4("[n]new name 0x%lx#%u, length=%u, count=%u: ",
  162.                  (ulong)pname, nidx, isize, ncnt);
  163.             for ( ci = 0; ci < isize; ci++ )
  164.                 dputc(ptr[ci]);
  165.             dputc('\n');
  166.         }
  167. #endif
  168.         ref_save(&the_nt->count, "name_ref(count)");
  169.         set_nt_count(the_nt, ncnt + 1);
  170.        }
  171.     /* Name was not in the table.  Make a new entry. */
  172.     if ( enterflag )
  173.     {    uint local = alloc_select_local(0);
  174.         cptr = (const byte *)alloc(size, 1, "name_ref(string)");
  175.         alloc_select_local(local);
  176.         if ( cptr == 0 )
  177.             return_error(e_VMerror);
  178.         memcpy((byte *)cptr, ptr, size);
  179.     }
  180.     else
  181.         cptr = ptr;
  182.     pname->string_size = size;
  183.     pname->string_bytes = cptr;
  184.     pname->pvalue = pv_no_defn;
  185.     make_name(pref, nidx, pname);
  186.     return 0;
  187. }
  188.  
  189. /* Get the string for a name. */
  190. void
  191. name_string_ref(const ref *pnref /* t_name */,
  192.   ref *psref /* result, t_string */)
  193. {    name *pname = pnref->value.pname;
  194.     make_const_string(psref, a_readonly, pname->string_size,
  195.               (const byte *)pname->string_bytes);
  196. }
  197.  
  198. /* Convert a t_string object to a name. */
  199. /* Copy the executable attribute. */
  200. int
  201. name_from_string(const ref *psref, ref *pnref)
  202. {    int exec = r_has_attr(psref, a_executable);
  203.     int code = name_ref(psref->value.bytes, r_size(psref), pnref, 1);
  204.     if ( code < 0 ) return code;
  205.     if ( exec ) r_set_attrs(pnref, a_executable);
  206.     return code;
  207. }
  208.  
  209. /* Enter a name during initialization. */
  210. /* Fatal error if the entry fails. */
  211. void
  212. name_enter(const char *str, ref *pref)
  213. {    if ( name_ref((const byte *)str, strlen(str), pref, 0) )
  214.         lprintf1("name_enter failed - %s", str),
  215.         gs_exit(1);
  216. }
  217.  
  218. /* Get the name with a given index. */
  219. void
  220. name_index_ref(uint index, ref *pnref)
  221. {    make_name(pnref, index, name_index_ptr(the_nt, index));
  222. }
  223.  
  224. /* Get the current name count. */
  225. uint
  226. name_count(void)
  227. {    return nt_count(the_nt);
  228. }
  229.  
  230. /* Check whether a name was created since a given count. */
  231. int
  232. name_is_since_count(const ref *pnref, uint cnt)
  233. {    return name_index_to_count(name_index(pnref)) >= cnt;
  234. }
  235.  
  236. /* Clean up the name table before a restore. */
  237. /* The count will be reset, and added subtables will be freed. */
  238. /* All we have to do is remove initial entries from the hash chains, */
  239. /* since we know they are linked in decreasing index order */
  240. /* (by sub-table, but not within each sub-table.) */
  241. /* (There will be some spurious non-zero entries in the subtable table, */
  242. /* but this doesn't matter since they will never be accessed.) */
  243. void
  244. name_restore(uint old_count)
  245. {    ushort *phash = &the_nt->hash[0];
  246.     uint old_sub = old_count & -nt_sub_size;
  247.     register uint i;
  248.     for ( i = 0; i < nt_hash_size; phash++, i++ )
  249.        {    register ushort *pnh = phash;
  250.         while ( *pnh >= old_sub )
  251.            {    if ( name_index_to_count(*pnh) < old_count )
  252.               pnh = &name_index_ptr(the_nt, *pnh)->next_index;
  253.             else
  254.                {
  255. #ifdef DEBUG
  256.                 if ( debug_c('n') | debug_c('U') )
  257.                   dprintf2("[n]restore remove name 0x%lx#%u\n",
  258.                        (ulong)name_index_ptr(the_nt, *pnh),
  259.                        (uint)*pnh);
  260. #endif
  261.                 *pnh = name_index_ptr(the_nt, *pnh)->next_index;
  262.                }
  263.            }
  264.        }
  265. }
  266.  
  267. /* ------ Internal procedures ------ */
  268.  
  269. /* Allocate the next sub-table. */
  270. private int
  271. name_alloc_sub(name_table *nt)
  272. {    uint local = alloc_select_local(0);
  273.     name *sub = (name *)alloc(1, sizeof(name_sub_table), "name_alloc_sub");
  274.     alloc_select_local(local);
  275.     if ( sub == 0 )
  276.         return_error(e_VMerror);
  277.     memset(sub, 0, sizeof(name_sub_table));
  278.     nt->table[nt_count(nt) >> nt_log2_sub_size] = sub;
  279.     return 0;
  280. }
  281.